#include "main.h"

#include <ctime>
#include <cstdlib>

inline void exchange(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

inline int choosePivot(int len)
{
	static double rr = 1.0 / RAND_MAX;

	int r = rand();
	double d = r * rr * (len-1);
	return (int)d;
}

/**
 * The pivot stays in the first place of array,
 * and j scans from begin to end
 */
int partition(int* array, int beg, int end)
{
	int pivotPos = choosePivot(end - beg + 1);
	exchange(array[beg], array[beg+pivotPos]);

	int pivot = array[beg];
	int i = beg, j = beg+1;
	for (; j <= end; ++j)
	{
		if (array[j] < pivot)
		{
			++i;
			exchange(array[j], array[i]);
		}
	}
	array[beg] = array[i];
	array[i] = pivot;

	return i;
}

/**
 * i scans from begin to end,
 * j scans from end to begin.
 * The pivot jumps between array[i] and array[j]
 */
int partition2(int* array, int beg, int end)
{
	int pivotPos = choosePivot(end - beg + 1);
	exchange(array[beg], array[beg+pivotPos]);

	int i = beg, j = end;
	while (true)
	{
		while (i < j && array[j] > array[i]) { j--; }
		if (i == j)	{ return i;	}

		if (array[i] != array[j]) { exchange(array[i], array[j]); }
		i++;

		while (i < j && array[i] < array[j]) { i++; }
		if (i == j) { return j; }
		
		if (array[i] != array[j]) { exchange(array[i], array[j]); }
		j--;
	}
}

void quickSort(int* array, int beg, int end)
{
	if (beg < end)
	{
		int pivotPos = partition2(array, beg, end);
		quickSort(array, beg, pivotPos-1);
		quickSort(array, pivotPos+1, end);
	}
}
